#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

// 使用快慢指针
class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }

        ListNode* slow = head;
        ListNode* fast = head->next;

        while (fast != slow) {
            if (fast == nullptr || fast->next == nullptr) {
                return false;
            }
            
            // slow每次走一步，fast每次走两步，如果有环，终会相遇
            slow = slow->next;
            fast = fast->next->next;
        }

        return true;
    }
};

int main() {
    ListNode* n1 = new ListNode(3);
    ListNode* n2 = new ListNode(2);
    ListNode* n3 = new ListNode(0);
    ListNode* n4 = new ListNode(4);

    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = n2;

    ListNode* head = n1;

    cout << Solution().hasCycle(head) << endl;

    return 0;
}